1. Field of the Invention
The embodiments described herein are related to methods for Low-Density Parity-Check decoding and more particularly to methods for achieving efficient and cost-effective Low-Density Parity-Check decoders.
2. Background of the Invention
A Low-Density Parity-Check (LDPC) code is an error correcting code that provides a method for transferring a message over a noisy transmission channel. While LDPC techniques cannot guaranty perfect transmission, they can be used to make the probability of lost information very small. In fact, LDPC codes were the first to allow data transmission rates at close to the theoretical maximum, e.g., the Shannon Limit. LDPC techniques use a sparse parity-check matrix, e.g, a matrix populated mostly with zeros; hence the term low-density. The sparse matrix is randomly generated subject to defined sparsity constraints.
LDPC codes can be defined in matrix and graphical form. An LDPC matrix will have a certain number of rows (N) and columns (M). The matrix can also be defined by the number of 1's in each row (wr) and the number of 1's in each column (wc). For a matrix to be considered low-density, the following conditions should be met: wc <<N and wr<<M. An LDPC matrix can also be regular or irregular. A regular LDPC matrix, or code is one in which wc is constant for every column and wr =wc*(N/M) is also constant for every row. If the matrix is low-density, but the number of 1's in each row or column are not constant, then such codes are called irregular LDPC codes.
It will also be understood that an LDPC code can be graphically defined by its corresponding Tanner graph. Not only do such graphs provide a complete representation of the code, they also help to describe the decoding algorithm as explained in more detail below. The nodes of the graph are separated into two distinctive sets called variable nodes (v-nodes) and check nodes (c-nodes). Thus, the Tanner graph will consist of M check nodes (the number of parity bits) and N variable nodes (the number of bits in a code word). A check node will then be connected to a variable node if there is a 1 in the corresponding element of the LDPC matrix.
The number of information bits can be represented as (K). Accordingly, the number of parity check bits M=N−K. A Generator Matrix (GN×K) can then be defined according to the following:GN×K=cN×1/dK×1 orcN×1=GN×K dK×1, wheredK×1=a message or date word, andcN×1=a code word.
As can be seen, the code word CN×1 is generated by multiplying the message by the generator matrix. The subscripts refer to the number of rows and columns, respectfully. Thus, the data word and code word can be represented as single-column matrices with K and N rows, respectfully.
The parity check Matrix can be defined as HM×NcN×1=0.
Accordingly, FIG. 1 is a diagram illustrating a system 100 that includes a transmitter and a receiver. A portion 102 of the transmitter and a portion 110 of the receiver are shown for simplicity. Referring to FIG. 1, an encoder 104 converts a data word dK×1 into a code word cN×1 via application of the generator matrix GN×K. Modulator 106 can be configured to then modulate code word cN×1 onto a carrier so that the code word can be wirelessly transmitted across channel 108 to the receiver.
In receive portion 110, demodulator 112 can be configured to remove the carrier from the received signal; however, channel 108 will add channel effects and noise, such that the signal produced by demodulator 112 can have the form: rN×1=2/σ2(1-2 cN×1)+wN×1, where r is a multilevel signal. As a result of the noise and channel effects, some of the data bits d will be lost in the transmission. In order to recover as much of the data as possible, decoder 114 can be configured to use the parity check matrix HM×N to produce an estimate {circumflex over (d)}K×1 of the data that is very close to the original data dK×1. It will be understood that decoder 114 can be a hard decision decoder or a soft decision decoder.
Unfortunately, conventional LDPC decoding techniques result in a high complexity, fully parallel decoder implementation where all the messages to and from all the parity node processors have to be computed at every iteration in the decoding process. This leads to large complexity, increased research requirements, and increased cost. Serializing part of the decoder by sharing a number of parity node processors is one option for reducing some of the overhead involved; however, serializing part of the decoder imposes stringent memory requirements to store the messages, resulting in an interconnection complexity bottleneck, i.e., complex interconnects between variable node, processors and parity node processors. Accordingly, serializing part of the decoder does not solve all of these problems.
Further, if different data rates are to be supported, then the decoder becomes even more complex in terms of memory size, memory architecture, and interconnect complexity. In general, another problem with conventional LDPC decoders is that the computations performed by the parity node processors are highly complex. Accordingly, these computations limit the speed of the decoder and increase its size and cost.